package model;

import java.util.HashMap;

/**
 * This class allows us to find a LCS using a greedy approach
 * 
 * @author Elias
 */
public class LCS_greedy {

	static StringBuffer lcs = new StringBuffer();
	static int aLen;
	static int bLen;
	static String a;
	static String b;
	static int lastIndexSelected = 0;
	static int indexOfFirstLetterOfXinY = 0;
	static int indexOfSecondLetterOfXinY = 0;
	static HashMap<String, Integer> list = new HashMap<String, Integer>();

	/**
	 * This function returns the lcs between x and y
	 * 
	 * @param x : the first sequence
	 * @param y : the second sequence
	 * @return the lcs
	 */
	public static String lcs(String x, String y) {
		lcs = new StringBuffer();
		lastIndexSelected = 0;
		indexOfFirstLetterOfXinY = 0;
		indexOfSecondLetterOfXinY = 0;
		list = new HashMap<String, Integer>();
		int idx;
		a = x;
		b = y;
		aLen = x.length();
		bLen = y.length();
		indexOfSecondLetterOfXinY = returnIndexOf(0);
		for (int i = 0; i < aLen; i++) {
			indexOfFirstLetterOfXinY = (lastIndexSelected == indexOfFirstLetterOfXinY) ? indexOfSecondLetterOfXinY
					: returnIndexOf(i);
			if (i + 1 < aLen) {
				indexOfSecondLetterOfXinY = returnIndexOf(i + 1);
				if (indexOfFirstLetterOfXinY > indexOfSecondLetterOfXinY) {
					idx = indexOfSecondLetterOfXinY;
					i++;
				} else {
					idx = indexOfFirstLetterOfXinY;
				}

				if (idx == bLen) {
					indexOfFirstLetterOfXinY = returnIndexOf(i);
				} else {
					lastIndexSelected = idx;
					lcs.append(a.charAt(i));
				}
			}

		}
		return lcs.toString();
	}

	/***
	 * This function returns the index in Y of the letter which is at the
	 * position index in X If the letter in X has a match on Y returns its
	 * position Else return bLen as an error case The index found in Y for a
	 * letter in X will be added inside the hashmap
	 * 
	 * @param index
	 * @return index
	 */
	public static int returnIndexOf(int index) {
		String s = Character.toString(a.charAt(index));
		int pos = (list.get(s) == null) ? 0 : list.get(s) + 1;
		pos = b.indexOf(s, pos > lastIndexSelected ? pos : lastIndexSelected);
		if (pos == -1) {
			pos = bLen;
		}
		list.put(s, pos);
		return pos;
	}

}
